package com.example.question.dp.dp5;

import java.util.Arrays;

public class Code01_740 {
    public static void main(String[] args) {
        Code01_740 code = new Code01_740();
        int res = code.deleteAndEarn1(new int[]{2, 2, 3, 3, 3, 4});
        System.out.println(res);
    }

    /**
     * 给你一个整数数组 nums ，你可以对它进行一些操作。
     * 每次操作中，选择任意一个 nums[i] ，删除它并获得 nums[i] 的点数。之后，你必须删除 所有 等于 nums[i] - 1 和 nums[i] + 1 的元素。
     * 开始你拥有 0 个点数。返回你能通过这些操作获得的最大点数。
     */
    public int deleteAndEarn1(int[] nums) {
        // 排序
        Arrays.sort(nums);
        int num = nums[0];
        int count = 1;
        Pair[] pairs = new Pair[nums.length];
        int index = 0;
        for (int i = 1; i < nums.length; i++) {
            if (nums[i] == num) {
                count++;
            } else {
                Pair pair = new Pair(num, count);
                pairs[index++] = pair;
                num = nums[i];
                count = 1;
            }
        }
        // 最后一次的
        Pair pair = new Pair(num, count);
        pairs[index] = pair;
        int[] dp = new int[index + 1];
        dp[0] = pairs[0].num * pairs[0].count;
        for (int i = 1; i < index + 1; i++) {
            Pair pair2 = pairs[i];
            if (pair2.num > pairs[i - 1].num + 1) {
                dp[i] = dp[i - 1] + pair2.count * pair2.num;
            } else {
                dp[i] = Math.max((i >= 2 ? dp[i - 2] : 0) + pair2.count * pair2.num, dp[i - 1]);
            }
        }
        return dp[index];
    }


    static class Pair {
        Integer num;
        Integer count;

        public Pair(Integer num, Integer count) {
            this.num = num;
            this.count = count;
        }
    }


    public int deleteAndEarn(int[] nums) {
        int[] numCount = new int[10001];
        for (int num : nums) {
            numCount[num] += num;
        }
        int[] dp = new int[10001];
        dp[0] = 0;
        dp[1] = numCount[1];
        for (int i = 2; i < numCount.length; i++) {
            dp[i] = Math.max(dp[i - 1], dp[i - 2] + numCount[i]);
        }
        return dp[numCount.length - 1];
    }

}
